#include<bits/stdc++.h>

using namespace std;

//sort a[left..right]
//T(n)=2*T(n/2)+O(n)=>T(n)=O(nlogn)
void quick_sort(int *a, int left, int right) {
    if (left >= right)return;//递归终点
    int i = left, j = right, pivot = a[left];
    while (i < j) {
        while (j > i && a[j] >= pivot)j--;//必须先移动尾部指针j否则会错误，思考下为什么
        while (i < j && a[i] <= pivot)i++;
        if (i >= j)break;
        swap(a[i], a[j]);
    }
    swap(a[left], a[i]);//哨兵pivot就位   数组分成了 用哨兵分隔的两部分，左边都比哨兵小，右边都比哨兵大
    quick_sort(a, left, i - 1);
    quick_sort(a, i + 1, right);
}

//C qsort comparator
int cmp(const void *p, const void *q) {
    int *ip = (int *) p;
    int *iq = (int *) q;
    return *ip - *iq;
}

int main() {
    int a[] = {1, 3, 4, 5, 7, 9, 2, 4, 6, 8, 0};
    size_t n = sizeof(a) / sizeof(a[0]);//size_t就是unsigned int
    //quick_sort(a, 0, n - 1);
    //stl qsort sort都是quick_sort
    sort(a, a + n);//C++ qsort
    qsort(a, n, sizeof(a[0]), cmp);//C语言的qsort
    copy(a, a + n, ostream_iterator<int>(cout, " "));
    cout << endl;
    return 0;
}
